package Array;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: Array
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-18  14:07
 * @Description: TODO
 * @Version: 1.0
 */
public class 多数元素169 {

    // 如果我们把众数记为 +1+1+1，把其他数记为 −1-1−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }

    public int majorityElement1(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i : nums) {
            if (!hashMap.containsKey(i)) {
                hashMap.put(i, 1);
            } else {
                if ((hashMap.get(i) + 1) > (nums.length / 2)) {
                    return i;
                } else {
                    hashMap.put(i, hashMap.get(i) + 1);
                }
            }
        }
        return Integer.MIN_VALUE;
    }

    public int majorityElement2(int[] nums) {
        // 基础方法市采用hasmp 来遍历整个数据来实现
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i : nums) {
            if (!hashMap.containsKey(i)) {
                hashMap.put(i, 1);
            } else {
                hashMap.put(i, hashMap.get(i) + 1);
            }
        }
        for (int i : hashMap.keySet()) {
            if (hashMap.get(i) > (nums.length / 2)) {
                return i;
            }
        }
        return Integer.MIN_VALUE;
    }

    public int majorityElement3(int[] nums) {
        // 排序完成后相关中间的数据可定是超过一半的
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}
